Критерий двудольности

Граф $G$ двудольный $\iff$ любой цикл в $G$ имеет четную длину.

$\Large{\implies}$ Пусть $(v_0, e_1, v_1, e_2, \ldots, e_k, v_k)$ — цикл в $G$, где $v_k = v_0$. Для любого $i$ вершины $v_i$ и $v_{i+1}$ принадлежат разным долям (по определению двудольности). Так как $v_0$ и $v_k$ находятся в одной доле, то длина цикла $k$ должна быть четной. $\Large{\impliedby}$ Пусть $G$ — граф, в котором все циклы имеют четную длину. Можно считать, что $G$ связен, так как граф двудолен, если все его компоненты связности двудольны. Пусть $d(u,v)$ (расстояние между $u$ и $v$) — наименьшая длина $(u,v)$-маршрута в $G$. Зафиксируем в $G$ произвольную вершину $u$. Рассмотрим две смежные вершины $v$ и $w$. Докажем, что $\delta = |d(u,v) - d(u,w)| = 1$. К любому $(u,v)$-маршруту можно добавить ребро $(v,w)$, получая $(u,w)$-маршрут на единицу большей длины, следовательно $d(u,w) \leq d(u,v) + 1$. Аналогично, $d(u,v) \leq d(u,w) + 1$. Отсюда $\delta \leq 1$. Докажем условие $\delta \neq 0$ от противного. Пусть $\delta = 0$, то есть $d(u,v) = d(u,w) = k$. Рассмотрим кратчайший $(u,v)$-путь и кратчайший $(u,w)$-путь. Пусть $v_i$ — последняя общая вершина этих путей, идущая от $u$. Тогда подграф, образованный путями от $v_i$ до $v$ и от $v_i$ до $w$, вместе с ребром $(v,w)$, содержит цикл $v_i \to \ldots \to v \to w \to \ldots \to v_i$. Длина этого цикла равна $(k-i) + (k-i) + 1 = 2(k-i)+1$, что является нечетным числом. Это противоречит условию теоремы. Итак, $\delta=1$, т.е. числа $d(u,v)$ и $d(u,w)$ имеют разную четность. Положим $X = \{v \in V \mid d(u,v) \text{ - нечетное}\}$ и $Y = \{v \in V \mid d(u,v) \text{ - четное}\}$. Тогда $\{X, Y\}$ — разбиение $V$. Поскольку для любых двух смежных вершин расстояние от $u$ до них имеет разную четность, одна из этих вершин лежит в $X$, а другая — в $Y$. Следовательно, граф $G$ по определению двудольный. $\square$